package code;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

public class WordLadder {
	/*
	 * bfsһ����������,start��endͬʱ����
	 * map<a,parent>vis,a�ĸ��ڵ�
	 * ˫����������TLE...
	 */
	
	public int ladderLength(String start, String end, Set<String> dict) {
		
		if(start.equals(end))	return 0;
		
		List<List<Integer>> edge=new ArrayList<List<Integer>>();
		
		ArrayList<String> nodeToString=new ArrayList<String>();
		Map<String,Integer> map=new HashMap<String,Integer>();
		
		if(!dict.contains(start))
			dict.add(start);
		if(!dict.contains(end))
			dict.add(end);
		Iterator it=dict.iterator();
		while(it.hasNext()){
			String s=(String) it.next();
			nodeToString.add(s);
			map.put(s, nodeToString.size()-1);
			edge.add(new ArrayList<Integer>());
		}
		
		it=dict.iterator();
		int i=0,j=0;
		/*
		 * ����Ҫԭ���ǣ�����n*n*len(s)���ȵĽ�������ڽӱ��ʱ��ʱ�为������
		 * ���ǵ�ÿ������ÿ��λ�õ�ֻ����a~z��26��Сд��ĸ������ö��һ��������һ�α仰�ĵ��ʣ��鿴�����ֵ������Ƿ�����Щ����
		 * �����ʱ�为���26^len*һ�β��Ĺ��
		 */
		int index=0;
		while(it.hasNext()){
			String s=(String) it.next();
			char[] array=s.toCharArray();
			String ss;
			for(i=0;i<s.length();i++){
				char oldChar=array[i];
				for(j=0;j<26;j++){
					char newChar=(char)(j+'a');
					if(oldChar==newChar)
						continue;
					array[i]=newChar;
					ss=new String(array);
					if(dict.contains(ss)){
						edge.get(index).add(map.get(ss));
					}
				}
				array[i]=oldChar;
			}
			index++;
		}
		
		/*
		 * ��start��ʼbfs��end����
		 */
		int from=map.get(start);
		int to=map.get(end);
		int n=dict.size();
		int[] distance=new int[n];
		int[] reverseDistance=new int[n];
		int[] pre=new int[n];
		
		Queue<Integer> queue=new LinkedList<Integer>();
		queue.add(from);
		
		List<List<String>> paths=new ArrayList<List<String>>();
		
		/*
		 * ��end��ʼbfs��start����
		 */
//		Queue<Integer> reverseQueue=new LinkedList<Integer>();
//		reverseQueue.add(map.get(end));
//		Map<Integer,Integer> reverseVis=new HashMap<Integer,Integer>();
		
		for(i=0;i<n;i++){
			distance[i]=Integer.MAX_VALUE;
			reverseDistance[i]=Integer.MAX_VALUE;;
		}
		distance[from]=0;
		reverseDistance[to]=0;
		
		while(!queue.isEmpty()){
			int head=queue.poll();
			List<Integer> ll=edge.get(head);
			for(i=0;i<edge.get(head).size();i++){
				int clover=edge.get(head).get(i);
				if(clover==to){
					return distance[head]+2;
				}
				if(distance[clover]>distance[head]+1){
					distance[clover]=distance[head]+1;
					queue.add(clover);
					pre[clover]=head;
				}
			}
		}
		
		return 0;
	}
	public boolean isOneStep(String s,String t){
		if(s.length()!=t.length())	return false;
		if(s.equals(t))	return false;
		int i;
		for(i=0;i<s.length();i++){
			if(t.charAt(i)!=s.charAt(i))	
				break;
		}
		//һ���в�һ����ַ�
		if(s.substring(i+1).equals(t.substring(i+1)))
			return true;
		return false;
	}
	
	
	public static void main(String[] args){
		Set<String> dict=new HashSet<String>();
		dict.add("hot");
		dict.add("dot");
		dict.add("lot");
		dict.add("dog");
		dict.add("log");
		String start="hit";
		String end="cog";
		WordLadder wd=new WordLadder();
		System.out.println(wd.ladderLength(start, end, dict));
	}
}
